package gameplaying;

import java.util.Scanner;

//每次能放的数最多是已经放的石子的平方，不能超过该箱子的容量
public class SquarePut1729 {

	public static void main(String[] args) {
		SquarePut1729 object = new SquarePut1729();
//		object.getRes();
		for(int i = 2; i <= 6; i++){
			System.out.println(object.getSG(27, i));
		}
	}
	
	
	//对于上限为S，当前容量为C
	//如果C + C * C < S && (C+1) + (C+1) * (C+1) >= S，那么对于（S,C）显然是一个必败态
	//找到最大的q，满足q + q * q < S(q为整数)，此时有(q + 1) * (q + 1) + (q + 1) >= s
	//如果C > q, 那么此时可以放完(前提是C < S)，是必胜态，所以此时的SG值是S - C，因为后继态包含(S, C + 1)~(S, S)
	//而这些态的SG值是从S - C - 1 ~ 0
	//如果C == q,则是必败态
	//如果C < q,那么说明此时不能放完。而在瓶子中已经有c个石头的前提下，容量为 s 和容量为 q的状态是等价的.
	//为什么是等价的呢，因为对于(q， C)一旦到达q，那么后者相当于面临的状态就是(S, q)
	//此时是必败的，所以前者获胜，所以先到达q的即为胜利
	//为什么SG值也是一样的呢？这个暂时不清楚
	//此时进行递归，求sg(q, C);
	
	public int getSG(int S, int C){
		int q = (int) Math.sqrt(S);
		while(q + q * q >= S){
			q--;
		}
		if(C > q){
			return S - C;
		}else{
			//不是很清楚这一步的原理
			return getSG(q, C);
		}
	}
	
	// Runtime: 327ms
	public void getRes(){
		Scanner scanner = new Scanner(System.in);
		int testCase = 1;
		while(scanner.hasNext()){
			int n = scanner.nextInt();
			int sum = 0;
			if(n == 0){
				break;
			}
			for(int i = 0; i < n; i++){
				int s = scanner.nextInt();
				int c = scanner.nextInt();
				sum ^= getSG(s, c);
			}
			System.out.println("Case " + testCase + ":");
			if(sum != 0){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
			testCase++;
		}
		scanner.close();
	}
}
